package algorithm.array;

import java.util.Arrays;

/**
 * leetcode : https://leetcode.com/problems/3sum-closest/description/
 * Difficulty : Medium
 *
 * 给一个数列nums，一个目标值target，求其中三个数字的和 最接近这个target 的 值。
 * 注意是求这个和，而不需要求这三个数列。
 * 题目描述：可以认为其中只有一个正确结果。（也就是说只有一个符合的结果）
 *
 * 借鉴3Sum的想法, 3Sum 会做的话，这个其实不难
 *
 * @Author Antony
 * @Since 2018/7/6 11:53
 */
public class ThreeSumClosest {

    public static void main(String[] args) {
        int[] num_1 = new int[]{0,1,2};
        int target_1 = 3;

        System.out.println(threeSumClosest(num_1, target_1));
    }

    /**
     * (leetcode beats 100%)
     * 时间复杂度 O(N^2)
     * 借鉴3Sum的思路
     *
     * 这里需要注意几个问题：
     *
     * 初始化数据：
     *  1、由于问题必须是3个元素的和，所以初始化最接近结果为前3个
     *  2、初始化最接近结果的差值是 closedResult - num[0]
     *
     * 终止条件：
     *  1、如果遇到differ==0 则可以提前终止
     *  2、如果没有遇到那只能是全部循环一遍了
     *
     * 声明变量：
     *  1、保存最接近的结果，以及结果的差值
     *  2、遍历时的临时Sum，临时Sum 和 target 之间的差值
     *
     */
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closedResult = nums[0] + nums[1] + nums[2];
        int closedDiffer = target - closedResult;
        int left, right, tmpSum, tmpDiffer;
        for(int i=0; i<nums.length; i++){
            if(i>1 && nums[i] == nums[i-1]){
                continue;
            }
            left = i+1;
            right = nums.length-1;
            while(left < right){
                tmpSum = nums[i] + nums[left] + nums[right];
                tmpDiffer = target - tmpSum;
                if(tmpDiffer == 0){
                    return tmpSum;  //如果为0，提前终止
                }
                if(abs(closedDiffer) > abs(tmpDiffer)){
                    closedDiffer = tmpDiffer;
                    closedResult = tmpSum;
                }
                if(tmpSum < target) left++;
                if(tmpSum > target) right--;
            }
        }
        return closedResult;
    }

    static int abs(int n){
        return n<0 ? 0-n : n;
    }

}
